# 介绍
动态规划是运筹学的一个分支，用于求解一个多阶段决策问题的最优解，适用于动态规划求解的问题，满足以下要求：
状态无后效性：某个阶段状态给定后，则该阶段以后过程的发展不受该阶段以前各阶段状态的影响
最优性原理：问题的一个最优决策序列的子序列也是最优的（通常利用“剪切”，来反证）
简单来说，就是一个问题需要满足：
重叠子问题：即可以被划分成规模更小的子问题
最优子问题：问题的最优解是由其子问题的最优解来构造的，且子问题间必须互相独立
动态规划的思想实质是分治思想和解决冗余
对比贪心算法：
- 动态规划：利用问题的最优子结构，自底向上从子问题的最优解逐步构造整个问题的最优解
- 贪心算法：虽然也利用问题的最优子结构，但是是以自顶向下的方式，先做选择再求解一个选出的子问题
# 回溯算法、贪心算法、动态规划比较
- 贪心算法：一条路走到黑，就一次机会，只能哪边看着顺眼走哪边
- 回溯算法：一条路走到黑，无数次重来的机会，还怕我走不出来 (Snapshot View)
- 动态规划：拥有上帝视角，手握无数平行宇宙的历史存档， 同时发展出无数个未来 (Versioned Archive View)